//Sunday, November 01 2009
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class MagicWords
{
	public:
		vector<int> mp;
		int count(vector <string> S, int K)
		{
			int ret = 0;
			for(int i=0; i<S.size(); i++)
				mp.push_back(i);
		//sort(mp.begin(), mp.end());
			do
			{
				string temp = "";
				for(int i=0; i<S.size(); i++)
					temp += S[mp[i]];
				if(check(temp, K))
					ret++;
			}
			while(next_permutation(mp.begin(), mp.end()));
			return ret;
		}

		bool check(string s, int K)
		{
// 		int cnt = 0;
// 		for(int i=0; i<s.size(); i++)
// 		{
// 			if(s[i] == s[0])
// 			{
// 				string temp = s.substr(i) + s.substr(0,i);
// 				if(temp.compare(s) == 0) cnt++;
// 			}
// 		}
//		return cnt==K;
			int d = (s.substr(1) + s).find(s) + 1;
			return K*d == s.size();
		}
};
